Strassen's-Matrix-Mutiplication

Problem Statement:

Given 2 matrix, multiply them such that the time complexity of the calculation is O(n^2.81). You can use divide and conquer approach to achieve the time complexity.

Algorithm Steps

1. Input Matrices: Given two n x n matrices, A and B.

2. Base Case:

   • If n = 1 , return the product A[0][0] x B[0][0] .

3. Divide:

   • Split each matrix into four n/2 x n/2 submatrices:

4. Compute Products:

   • Calculate the following seven products:
     1. P₁ = A₁₁ x (B₁₂ - B₂₂)
     2. P₂ = (A₁₁ + A₁₂) x B₂₂
     3. P₃ = (A₂₁ + A₂₂) x B₁₁
     4. P₄ = A₂₂ x (B₂₁ - B₁₁)
     5. P₅ = (A₁₁ + A₂₂) x (B₁₁ + B₂₂)
     6. P₆ = (A₁₂ - A₂₂) x (B₂₁ + B₂₂)
     7. P₇ = (A₁₁ - A₂₁) x (B₁₁ + B₁₂)

5. Combine Results:

   • Compute the four submatrices of the resulting product:
     • C₁₁ = P₅ + P₄ - P₂ + P₆
     • C₁₂ = P₁ + P₂
     • C₂₁ = P₃ + P₄
     • C₂₂ = P₅ + P₁ - P₃ - P₇

6. Combine Submatrices:

   • Construct the final resulting matrix C from the submatrices.

7. Output: Return the resulting matrix C .

Time Complexity:

• The time complexity of Strassen's algorithm for matrix multiplication is O(n^2.81). This is an improvement over the conventional matrix multiplication's. Strassen's algorithm reduces the number of multiplicative operations by recursively dividing matrices into smaller submatrices, making it more efficient for large matrices, though it may incur overhead from additional additions and subtractions.

Space Complexity:

• The space complexity of Strassen's matrix multiplication algorithm is O(n), where n is the dimension of the matrices. This complexity arises from the additional space needed to store the temporary matrices used in the recursive calculations. While Strassen's algorithm requires fewer multiplicative operations, it still utilizes linear space to hold the intermediate results, making it more space-efficient than traditional methods, which typically require O(n^2) space for the resulting matrix.

Sample Input:

Enter the elements of the first matrix (2x2): 5 10 15 20 Enter the elements of the second matrix (2x2): 6 8 9 2

Sample Output:

The resultant matrix is: 120 60 270 160

C++ Implementation:

#include <iostream>
using namespace std;

int main() {
    int matrixA[2][2], matrixB[2][2], resultMatrix[2][2];
    int p1, p2, p3, p4, p5, p6, p7;
    
    cout << "Enter the elements of the first matrix (2x2):\n";
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++)
            cin >> matrixA[i][j];
    }

    cout << "Enter the elements of the second matrix (2x2):\n";
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++)
            cin >> matrixB[i][j];
    }


    p1 = (matrixA[0][0] + matrixA[1][1]) * (matrixB[0][0] + matrixB[1][1]);
    p2 = (matrixA[1][0] + matrixA[1][1]) * matrixB[0][0];
    p3 = matrixA[0][0] * (matrixB[0][1] - matrixB[1][1]);
    p4 = matrixA[1][1] * (matrixB[1][0] - matrixB[0][0]);
    p5 = (matrixA[0][0] + matrixA[0][1]) * matrixB[1][1];
    p6 = (matrixA[1][0] - matrixA[0][0]) * (matrixB[0][0] + matrixB[0][1]);
    p7 = (matrixA[0][1] - matrixA[1][1]) * (matrixB[1][0] + matrixB[1][1]);

    resultMatrix[0][0] = p1 + p4 - p5 + p7;
    resultMatrix[0][1] = p3 + p5;
    resultMatrix[1][0] = p2 + p4;
    resultMatrix[1][1] = p1 - p2 + p3 + p6;

    cout << "\nThe resultant matrix is:\n";
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++)
            cout << resultMatrix[i][j] << "\t";
        cout << "\n";
    }

    return 0;
}